Cách biểu diễn thông thường của các bài toán quyết định là tập hợp các đối tượng thỏa mãn tính chất đang xét. Tập dừng

K:= {(i, x) | chương trình i với dữ liệu vào x dừng trong hữu hạn bước}

đại diện cho bài toán dừng.

Có nhiều định nghĩa tương đương của bài toán dừng. Tất cả các tập có bậc Turing bằng với bài toán dừng là một cách định nghĩa. Sau đây là một vài ví dụ:

• { i | chương trình i dừng khi chạy trên dữ liệu vào 0 }
• { i | tồn tại dữ liệu vào x sao cho chương trình i dừng khi chạy trên dữ liệu x }